/**
 * @file 226.InvertBinaryTree.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-12
 *
 * @copyright Copyright (c) 2021
 *
 * 简单二叉树 一般而言都可以用递归和迭代
 * 226.翻转二叉树
 * 100.相同的树
 * 101.对称二叉树
 * 572.另一棵树的子树
 */

#include <algorithm>
#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
  public:
    // 226. 一题三解 递归+层序+前序，吊打Max Howell
    TreeNode *invertTree(TreeNode *root)
    {
        if (!root) {
            return nullptr;
        }
        // 先保存结果
        TreeNode *left = invertTree(root->left);
        TreeNode *right = invertTree(root->right);
        root->right = left;
        root->left = right;
        return root;
    }
    TreeNode *invertTreeLevel(TreeNode *root)
    {
        // 对每个节点来说，都需要交换一下左右孩子
        // 因此，也可以用层序遍历
        queue<TreeNode *> q;
        if (root) {
            q.push(root);
        }
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                TreeNode *node = q.front();
                q.pop();
                // swap 每个节点的左右孩子
                TreeNode *temp = node->left;
                node->left = node->right;
                node->right = temp;
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
        }
        return root;
    }
    TreeNode *invertTreePreorder(TreeNode *root)
    {
        // 对每个节点来说，都需要交换一下左右孩子
        // 因此，也可以用前序遍历
        stack<TreeNode *> stk;
        if (root) {
            stk.push(root);
        }
        while (!stk.empty()) {
            TreeNode *node = stk.top();
            stk.pop();
            // swap
            TreeNode *temp = node->left;
            node->left = node->right;
            node->right = temp;
            if (node->right) {
                stk.push(node->right);
            }
            if (node->left) {
                stk.push(node->left);
            }
        }
        return root;
    }

    // 100.
    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        // 递归
        if (!p && !q) {
            return true;
        } else if (!p || !q || p->val != q->val) {
            return false;
        } else {
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
    // 100. 迭代
    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        // 层序
        queue<TreeNode *> q1;
        queue<TreeNode *> q2;
        q1.push(p);
        q2.push(q);
        while (!q1.empty() && !q2.empty()) {
            TreeNode *u = q1.front();
            q1.pop();
            TreeNode *v = q2.front();
            q2.pop();
            if (!u && !v) { // 均是空节点
                continue;
            } else if (!u || !v || u->val != v->val) { // 有一空或值不同
                return false;
            } else { // 均非空，左右孩子入队
                q1.push(u->left);
                q1.push(u->right);
                q2.push(v->left);
                q2.push(v->right);
            }
        }
        return true;
    }
    // 101. 递归
    bool isSymmetric(TreeNode *root)
    {
        // 对称 左==右
        if (!root) {
            return true;
        }
        return isSymmetric(root->left, root->right);
    }

  private:
    bool isSymmetric(TreeNode *left, TreeNode *right)
    {
        if (!left && !right) {
            return true;
        } else if (!left || !right || left->val != right->val) {
            return false;
        } else {
            // 左 == 右
            // 递归 看清楚谁和谁相比
            return isSymmetric(left->left, right->right) && isSymmetric(right->left, left->right);
        }
    }

  public:
    // 101. 迭代 层次遍历
    bool isSymmetric2(TreeNode *root)
    {
        // 层次遍历 每次把一层首尾元素加入队列
        queue<TreeNode *> q;
        if (root) {
            q.push(root->left);
            q.push(root->right);
        }
        while (!q.empty()) {
            TreeNode *u = q.front();
            q.pop();
            TreeNode *v = q.front();
            q.pop();
            if (!u && !v) {
                continue;
            } else if (!u || !v || u->val != v->val) {
                return false;
            } else { // 左右右左
                q.push(u->left);
                q.push(v->right);
                q.push(u->right);
                q.push(v->left);
            }
        }
        return true;
    }
    // 572. 递归好理解，非递归就算了
    // 三种可能：
    // subRoot和root是同一棵树，subRoot是root左子树的子树，subRoot是root右子树的子树
    bool isSubtree(TreeNode *root, TreeNode *subRoot)
    {
        if (!root && !subRoot) {
            return true;
        } else if (!root && subRoot) {
            return false;
        } else {
            return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
        }
    }
};